#include "dataStructuresHeader.h"
#include "bst.h"
int insertBSTWhileMount(int iterDescriptors,descriptors desc[])
{
	root=NULL;
	int bstRet=0;
	int i;
	for(i=0;i<iterDescriptors;i++)
	{
		if(desc[i].type=='f')
		{
			absolutePathForBST=(char*)malloc(sizeof(char)*(strlen(desc[i].location)+1+strlen(desc[i].fileName)+1));
			if(strcmp(desc[i].location,"/")!=0)
				sprintf(absolutePathForBST,"%s/%s",desc[i].location,desc[i].fileName);
			else
				sprintf(absolutePathForBST,"%s%s",desc[i].location,desc[i].fileName);
			bstRet=insertBST(absolutePathForBST,desc[i].blockNumber); // inserts into binary search tree
			if(bstRet!=0)
			{
				return -1;
			}
			bstRet=0;
		}
	}
	return bstRet;
}
void SubInsert( struct bst *currentroot ,struct bst *nodetoInsert)
{
	//check if node.abspath is less than the currentroot.abspath and Insert it to left  if true
	if(strcmp(nodetoInsert->abspath,currentroot->abspath)<0){
			if(currentroot->left != NULL)
			   SubInsert( currentroot->left,nodetoInsert);
			else{
				currentroot->left = nodetoInsert ;
				nodetoInsert->parent = currentroot ;
				//printf("%s  Node successfully Inserted in the left part of BST\n",nodetoInsert->abspath);
			}
		}
		//check if node.abspath is greater than the currentroot.abspath and Insert it to right if true
        else if(strcmp(nodetoInsert->abspath,currentroot->abspath)>0){
			if(currentroot->right != NULL)
			   SubInsert( currentroot->right,nodetoInsert);
			else{
				currentroot->right = nodetoInsert ;
				nodetoInsert->parent = currentroot ;
				//printf("%s Node successfully Inserted in the right part of BST\n",nodetoInsert->abspath);
			}
		}
}

int insertBST(char abspath[],long blockNumber)
{
	int ret=-1;
	struct bst *node = NULL ,*currentroot = NULL ;
	node = (struct bst*)malloc(sizeof(struct bst));
	if(node != NULL)
	{
		//node->abspath = abspath ;
		strcpy(node->abspath , abspath);
		node->blockNumber=blockNumber;
		node->left = NULL ;
		node->right = NULL ;
		node->parent = NULL ;
	}
	else
	{
		ret=-2;
		//printf("Out of memory :Could not allocate space for root node!! \n" );
		return ret;
	}
	if(root == NULL)
	{
		root = node ;
		ret=0;
		//printf("%s  is the first node Inserted to root\n",root->abspath);
	}
	else
	{
		currentroot = root;
		SubInsert(currentroot ,node);
		ret=0;
	}
	return ret;
}
//returns -1 if node is not present in the BST
long subSearch(struct bst *root,char abspath[] )
{
	if(root != NULL){
		if(strcmp(abspath,root->abspath)<0){
			subSearch(root->left,abspath);
		}
		else if (strcmp(abspath , root->abspath)>0){
			subSearch(root->right,abspath);
		}
		else if(strcmp(abspath , root->abspath)==0){
			return root->blockNumber;
		}

	}
	else
		return -1;

}

void displayBST(struct bst *root)
{
	//inorder
	if(root != NULL){
		displayBST(root->left);
	    printf("%s \n",root->abspath);
	    displayBST(root->right);
	}

}

descriptors* searchBST(char abspath[])
{
	long blockNumOfFile = -1;
	int NoOfFileDescriptors = 0 ;
	int count = 0 ;
	long temp = 0;
	descriptors *tempy =(descriptors*)malloc(sizeof(descriptors));

	blockNumOfFile = subSearch(root,abspath);
	if(blockNumOfFile != -1)
	{
		NoOfFileDescriptors = mh->countOfFileDescriptors;
		int maxFDs=mh->maxDescriptors;
		while( count < maxFDs)
		{
			if(h->desc[count].blockNumber == blockNumOfFile)
			{
				tempy = &h->desc[count];
				return &h->desc[count];
			}
			count++ ;
		}
	}
	return  NULL;
}

//returns the minimum node in the right subtree of node
struct bst* findSuccessor(struct bst *node)
{
    if(node == NULL)
	return node;
    if(node->left != NULL)
	return findSuccessor(node->left);//rets the leftmost child
    else
    return node ;
 }

struct bst* getNode(struct bst *root,char abspath[] )
{
 while(root != NULL){
  if(strcmp(root->abspath,abspath)==0)
	  return root ;
  else if(strcmp(abspath , root->abspath)<0)
	  root = root->left ;
  else if(strcmp(abspath ,root->abspath)>0)
	  root = root->right ;

}
return NULL ;
}

int subDeleteNode(struct bst *root,char abspath[])
{
	int deleted = FALSE ;
    struct bst *temp = NULL;
	 root = getNode(root , abspath );
	if(root != NULL){
	if(root->left && root->right){ //node has 2 children
			temp = findSuccessor(root->right);
			strcpy(root->abspath,temp->abspath);
			root->blockNumber = temp->blockNumber;
			//free the temp node
			subDeleteNode(temp,temp->abspath);
	}
	else if((root->left) && (root->right) == NULL){ //node has left child only
		//if root is the left child of parent then replace at the left node of parent
		if(root == root->parent->left)
		{
	    root->parent->left = root->left;
	    root = NULL ;
	    free(root);
		deleted = TRUE ;
		}//if root is the right child of parent then replace at the right node of parent
		else if(root == root->parent->right){
		root->parent->right = root->left;
	    root = NULL ;
	    free(root);
		deleted = TRUE ;
		}

	}
	else if((root->right) && (root->left) == NULL){//node has right child only
		//if root is the left child of parent then replace at the left node of parent
		if(root == root->parent->left)
		{
	    root->parent->left = root->right;
	    root = NULL ;
	    free(root);
		deleted = TRUE ;
		}//if root is the right child of parent then replace at the right node of parent
		else if(root == root->parent->right){
		root->parent->right = root->right;
	    root = NULL ;
	    free(root);
		deleted = TRUE ;
		}

	}
	else{ //node has no children
		if((root->parent->left != NULL)&&(root->parent->left->abspath == root->abspath))
			root->parent->left = NULL ;
		else if ((root->parent->right != NULL)&&(root->parent->right->abspath == root->abspath))
		   root->parent->right = NULL ;

	       root = NULL ;
	       free(root);
		   deleted = TRUE ;
	}
}
	return deleted; // if deleted is false node was not found to be deleted
}
//delete function will not have root parameter therefore subdeletenode()function with root parameter is introduced
int deletenodeBST(char abspath[] )
{
	return subDeleteNode(root,abspath);
}
